﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Task6
{
    public class Graph
    {
        private int[][] childNodes;
        private bool[] visited;

        private List<int> currentConnectedComponents;
        private List<List<int>> foundCycles;

        public Int32 NodesCount
        {
            get
            {
                return this.childNodes.Length;
            }
        }

        public Int32[][] Childs
        {
            get
            {
                return this.childNodes;
            }
        }

        public Graph(int[][] nodes)
        {
            this.childNodes = nodes;
            this.visited = new bool[childNodes.GetLength(0)];
            this.currentConnectedComponents = new List<int>();
            this.foundCycles = new List<List<int>>();

        }

        private void FindAllConnectedComponents(int startNode)
        {
            visited[startNode] = true;

            foreach (int node in childNodes[startNode])
            {
                if (!visited[node])
                {
                    currentConnectedComponents.Add(node);
                    FindAllConnectedComponents(node);
                }
            }
        }

        private void AddConnectedComponents(List<int> connectedComponents)
        {
            List<int> groupsOfConnectedComponents = new List<int>();
            foreach (int node in connectedComponents)
            {
                groupsOfConnectedComponents.Add(node);
            }

            foundCycles.Add(groupsOfConnectedComponents);
        }

        public void PrintAllCycles()
        {
            for (int node = 0; node < childNodes.GetLength(0); node++)
            {
                if (!visited[node])
                {
                    currentConnectedComponents = new List<int>();
                    currentConnectedComponents.Add(node);
                    visited[node] = true;
                    FindAllConnectedComponents(node);
                    AddConnectedComponents(currentConnectedComponents);
                }
            }

            foreach (List<int> lstPath in foundCycles)
            {
                foreach (int node in lstPath)
                {
                    Console.Write(node + " ");
                }
                Console.WriteLine();
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph g = new Graph(new int[][] {
                                              new int[] {3, 6}, // successors of vertice 0
                                              new int[] {2, 3, 4, 5, 6}, // successors of vertice 1
                                              new int[] {1, 4, 5}, // successors of vertice 2
                                              new int[] {0, 1, 5}, // successors of vertice 3
                                              new int[] {1, 2, 6}, // successors of vertice 4
                                              new int[] {1, 2, 3}, // successors of vertice 5
                                              new int[] {0, 1, 4},  // successors of vertice 6
                                              new int[] {7}
                                            });

            bool[] visited = new bool[g.NodesCount];

            g.PrintAllCycles();
        }
    }
}
